package com.zjsru.oneDay202211;

/**
 * @Author: CookLee
 * @Date: 2022/11/16
 * 全局倒置与局部倒置
 * 全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
 * 0 <= i < j < n
 * nums[i] > nums[j]
 *
 * 局部倒置 的数目等于满足下述条件的下标 i 的数目：
 * 0 <= i < n - 1
 * nums[i] > nums[i + 1]
 *
 * 输入：nums = [1,0,2]
 * 输出：true
 * 解释：有 1 个全局倒置，和 1 个局部倒置。
 *
 * 输入：nums = [1,2,0]
 * 输出：false
 * 解释：有 2 个全局倒置，和 1 个局部倒置。
 *
 */
public class IsIdealPermutation {
    /**
     * 局部倒置 包含于全局倒置,观察 非相邻数字是否满足递增(非局部倒置) 如果满足则返回false
     * //判断除了局部逆序对还有其他逆序对就可以返回false
     */
    public boolean isIdealPermutation(int[] nums) {
        int max = nums[0];
        //非相邻数字
        for (int i = 2; i < nums.length; i++) {
            //没有大于第一个数 代表没有全局倒置
            if (nums[i] < max) {
                return false;
            }
            max = Math.max(nums[i - 1], max);
        }
        return true;
    }
    
    /**
     * 数学
     * <p>
     * 【差值等于0】表示元素i所在的位置就是排序后的位置。 【差值等于1】表示元素1所在的位置向前1位或向后1位。 【其他情况】表示元素所在位置偏差大于1位，也就是出现了全局倒置并且非局部倒置的情况。
     **/
    public boolean isIdealPermutation2(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
    
    
    public static void main(String[] args) {
        IsIdealPermutation isIdealPermutation = new IsIdealPermutation();
        int[] nums = new int[]{1,0,2};
        System.out.println(isIdealPermutation.isIdealPermutation(nums));
    }
}
